__author__ = 'cain76'
import random


def gen_maze(ww, hh, spx=None, spy=None, epx=None, epy=None):
    def _idx(x_, y_, w_): return x_ + y_ * w_

    def append4way(__way, x_, y_):
        __ii = random.randint(0, 3)
        __cnt = 0
        while __cnt < 4:
            __tt = __ii % 4
            if __tt == 0: __way.append((x_, y_, x_, y_ + 2, 0, 1))
            if __tt == 1: __way.append((x_, y_, x_ + 2, y_, 1, 0))
            if __tt == 2: __way.append((x_, y_, x_, y_ - 2, 0, -1))
            if __tt == 3: __way.append((x_, y_, x_ - 2, y_, -1, 0))
            __ii += 1
            __cnt += 1
        return __way

    if spx is None: spx = random.randrange(ww // 2) * 2
    if spy is None: spy = random.randrange(hh // 2) * 2

    if epx is None: epx = random.randrange(ww // 2) * 2
    if epy is None: epy = random.randrange(hh // 2) * 2

    maze = []
    for idx in range(ww * hh): maze.append(0)
    way = []
    way = append4way(way, spx, spy)
    maze[_idx(spx, spy, ww)] = 3
    while len(way) > 0:
        cx, cy, wx, wy, tx, ty = way.pop()
        if 0 > wx: continue
        if wx >= ww: continue
        if 0 > wy: continue
        if wy >= hh: continue
        if maze[_idx(wx, wy, ww)] > 1: continue

        maze[_idx(cx + tx, cy + ty, ww)] = 2
        if wx == epx and wy == epy:
            maze[_idx(wx, wy, ww)] = 4
            continue
        else:
            maze[_idx(wx, wy, ww)] = 2
            way = append4way(way, wx, wy)
    # print_maze(maze, ww, hh)
    return maze, spx, spy, epx, epy


def print_maze(m, W, H):
    for yy in range(H):
        for xx in range(W):
            if m[yy * W + xx] == 3: print('S', end='')
            elif m[yy * W + xx] == 4: print('E', end='')
            elif m[yy * W + xx] > 1: print('#', end='')
            else: print('.', end='')
        print('\n', end='')

if __name__ == '__main__':
    w = 21
    h = 11
    mm = gen_maze(w, h)
    print_maze(mm[0], w, h)